# include<stdio.h>
# include<malloc.h>
# include<stdlib.h>
 
 
# define TRUE 1
# define FALSE 0
# define OK 1
# define ERROR 0
# define INFEASIBLE -1
# define OVERFLOW -2
 
 
typedef int Status;
typedef char ElemType;
 
 
//定义单链表的存储结构
typedef struct LNode
{
	ElemType date;
	struct LNode *next; 
}LNode , *LinkList;
//构造一个单链表
Status InitList(LinkList &L)
{
	L=(LinkList)malloc(sizeof(LNode));//生成结点
	if(!L)
	{
		return OVERFLOW;
	}
	L->next = NULL;
	return OK;
}
//销毁单链表
Status DestroyList(LinkList &L)
{
	LinkList q = L;
	while(q != NULL)
	{
		LinkList p = q;
		q = q->next;
		free(p);
		p = NULL;
	}
	return OK;
}
//判断是否为空，为空返回ture,否则返回false
Status ListEmpty(LinkList L)
{
	if(!L->next)//为空
	{
		return TRUE;
	}
	else
		return FALSE;
}
//返回单链表的长度
Status ListLength(LinkList L)
{
	int i = 0;
	LNode * p;
	p = L->next;
	while(p != NULL)
	{
		i++;
		p = p->next;
	}
	return i;
}
//打印单链表中的元素
void DispList(LinkList &L)
{
  LinkList p;
  p = L->next;
  while(p != NULL)
  {
	  printf("%c" , p->date);
	  p = p->next;
  }
  printf("\n");
}
//从单链表L中查找第i个元素，由参数e返回其元素的值
Status GetElem(LinkList L , int i , ElemType &e)
{
	int j = 1; 
	struct LNode *p = L->next;
	while(p && j<i)
	{
		p = p->next;
		++j;
	}
	if(!p || j>i) //第i个元素不存在
	{
	  return ERROR;
	}
	e = p->date;  //取第i个元素
	return OK;
}
//在单链表L中查找元素e的位置，不存在则返回0
Status LocateElem(LinkList L, ElemType e)
{
	int i = 0;
	LinkList p = L->next;
	while (p)
	{
		i++;
		if (p->date == e)
		{
			return i;
		}
		p = p->next;
	}
	return 0;
 
}
//在单链表L中第i个位置之前插入元素e
Status ListInsert(LinkList &L, int i, ElemType e)
{
	int j = 0;
	LinkList p = L, s;
	while (p && j<i-1)
	{ 
		p = p->next;
		++j;
	}
	if (!p || j>i-1)
	{
		return ERROR;
	}
	s = (LinkList)malloc(sizeof(LNode));//生成新节点
	s->date = e;
	s->next = p->next; //把所有元素向后移一位
	p->next = s;
	return OK;
}
//单链表L中删除第i个元素，并由e返回其值
Status ListDelete(LinkList &L, int i, ElemType &e)
{
	int j = 0;
	LinkList p = L, q;
	while (p->next && j<i-1)
	{
		p = p->next;
		++j;
	}
	if (!(p->next) || j>i-1)
	{
		return ERROR;
	}
	q = p->next;
	p->next = q->next;
	e = q->date;
	free(q);
		return OK;
}
int main()  
{  
    int l;  
    LinkList(L);  
    ElemType e;  
    printf("<1>初始单链表L\n");  
    InitList(L);  
    printf("<2>依次采用尾插法插入a , b , c , d , e元素\n");  
    ListInsert(L , 1 , 'a');  
    ListInsert(L , 2 , 'b');  
    ListInsert(L , 3 , 'c');  
    ListInsert(L , 4 , 'd');  
    ListInsert(L , 5 , 'e');  
    printf("<3>输出单链表L:");  
    DispList(L);  
    l=ListLength(L);  
    printf("<4>单链表长度l=%d\n" , l);  
    printf("<5>单链表L为%s\n" , (ListEmpty(L)?"空":"非空"));  
    GetElem(L , 3 , e);  
    printf("<6>单链表的第3个元素=%c\n" , e);  
    printf ("<7>元素a的位置=%d\n" , LocateElem(L , 'a'));  
    printf("<8>在第4个元素位置上插入f元素\n");  
    ListInsert(L , 4 , 'f');  
    printf("<9>单链顺序表L:");  
    DispList(L);  
    printf("<10>删除L的第3个元素\n");  
    ListDelete(L , 3 , e);  
    printf("<11>输出单链表L:");  
    DispList(L);  
    printf("<12>释放单链表L\n");  
    free(L);  
  
return 0;   
}   